背包动态规划复习
01背包
考虑到最多只能选取1个,反向枚举顺序满足当前决策不会影响到同一个物品的其他决策。
朴素枚举
for(int i=1;i<=n;i++) for(int j=V;j>=v[i];j--){
dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
}
Nothing with me, but Forever.
本着来写状压的,奈何发现手算一波复杂度后感觉不对。
那么我们考虑搜索(n≤10),暴力搞的话复杂度为 O(n!×T),无法通过。
那么我们考虑使用一点点的状压思想和搜索技巧:
给定一个序列的线性递推式:
fn=⎩⎪⎨⎪⎧a⋅fn−1+b⋅fn−2f1f0,,,n≥2n=1n=0
多组询问,给定 n,a,b,f0,f1,求 fn 的值。